package tarjan;

import java.util.Scanner;

/*1p302,测试数据，保证不存在重复边和反向边
7 7
1 2 5
2 3 7
3 5 2
5 7 9
5 6 3
6 4 8
4 1 4
*/
/*1p272,测试数据，保证不存在重复边和反向边
4 5
1 2 5
2 3 8
2 4 12
3 4 9
4 1 3
*/
//Tarjan无向图桥与割点
public class QiaoGedian {
	//链式前向星保存图数据
	static int maxv = 101;
	static int maxe = 101;
	//头节点数组
	static int[] head = new int[maxv];
	//边集数组
	static Edge[] edge = new Edge[maxe];
	//边数组的下标
	static int cnt = 0;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		//初始化头节点数组
		for(int i=0;i<maxv;i++) {
			head[i] = -1;
		}
		//获取全部边数据
		for(int i=0;i<m;i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();
			
			//无向图添加反向边
			add(u,v,w);
			add(v,u,w);
		}
		//打印链式前向星图
		for(int i=1;i<=n;i++) {
			System.out.printf("head[%d]:%d",i,head[i]);
			for(int j=head[i];j!=-1;j=edge[j].next) {
				System.out.printf("-->(to:%d,w:%d,next:%d)",edge[j].to,edge[j].w,edge[j].next);
			}
			System.out.printf("\n");
		}
		System.out.println("--------------------");
		
		
		//tarjan_qiao(1,1);
		//tarjan_reset();
		//System.out.println();
		tarjan_gedian(1,1);
	}
	
	//添加边的方法
	static void add(int u,int v,int w) {
		
        //edge[cnt].to = u;
        //edge[cnt].w = w;
        //节点前插
        //edge[cnt].next = head[u];
		edge[cnt] = new Edge(v,head[u],w);

		//head[u]更新为当前边的数组下标
		head[u] = cnt;
		//下标加1
		cnt++;
	}
	
	
	//时间戳
	static int[] dfn = new int[maxv];
	//追溯点
	static int[] low = new int[maxv];
	//计数器
	static int num = 0;
	//初始化Tarjan算法共用变量，dfn[]，low[]，num
	static void tarjan_reset() {
		for(int i=0;i<maxv;i++) {
			dfn[i] = 0;
			low[i] = 0;
		}
		num = 0;
	}
	
	//无向图桥Tarjan算法
	//u:节点编号
	//fa:u节点在DFS遍历树上的父
	static void tarjan_qiao(int u,int fa) {
		num++;
		dfn[u] = num;
		low[u] = num;
		//遍历该节点的边
		for(int i=head[u];i!=-1;i=edge[i].next) {
			int v = edge[i].to; //连接的点
			if(v==fa) //排除父节点
				continue;
			if(dfn[v]==0) {//没有访问过的点
				//dfs搜索
				//u为v的父
				tarjan_qiao(v,u);
				//回溯时更新追溯点
				low[u] = Math.min(low[u], low[v]);
				if(low[v]>dfn[u]) //桥判断条件
					System.out.printf("%d--%d是桥", u, v);
			}else {//访问过的点
				low[u] = Math.min(low[u], dfn[v]);
			}
		}
	}
	
	//无向图割点Tarjan算法
	//u:节点编号
	//fa:u节点在DFS遍历树上的父
	static void tarjan_gedian(int u,int fa) {
		num++;
		dfn[u] = num;
		low[u] = num;
		//计数
		int count = 0;
		//遍历该节点的边
		for(int i=head[u];i!=-1;i=edge[i].next) {
			int v = edge[i].to; //连接的点
			if(v==fa) //排除父节点
				continue;
			if(dfn[v]==0) {//没有访问过的点
				//dfs搜索
				//u为v的父
				tarjan_gedian(v,u);
				//回溯时更新追溯点
				low[u] = Math.min(low[u], low[v]);
				
				//割点判断条件
				if(low[v]>=dfn[u]) {
					//符合条件的子节点做计数
					count++;
					if(u!=fa||count>1) {
						System.out.printf("%d是割点", u, v);
					}
				}
				
			}else {//访问过的点
				low[u] = Math.min(low[u], dfn[v]);
			}
		}
	}
}
